import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SolutionLCP8 {
    public int[] getTriggerTime(int[][] increase, int[][] requirements) {
        int x=0,y=0,z=0;
        List<int[]> list=new ArrayList<>();
        list.add(new int[]{x,y,z});
        for (int[] ints : increase) {
            x+=ints[0];
            y+=ints[1];
            z+=ints[2];
            list.add(new int[]{x,y,z});
        }
        int[] ans=new int[requirements.length];
        for (int i=0;i<requirements.length;i++){
            int a=search(list,0,0,requirements[i][0]);
            a=search(list,a,1,requirements[i][1]);
            a=search(list,a,2,requirements[i][2]);
            ans[i]=a;
        }
        return ans;
    }

    private int search(List<int[]> list, int start, int k, int limit) {
        if (start==-1){
            return -1;
        }
        int l=start,r=list.size()-1,ans=-1;
        while (l<=r){
            int mid=(l+r)/2;
            if (list.get(mid)[k]>=limit){
                ans=mid;
                r=mid-1;
            }else {
                l=mid+1;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new SolutionLCP8().getTriggerTime(new int[][]{{2, 8, 4}, {2, 5, 0}, {10, 9, 8}}, new int[][]{{2, 11, 3}, {15, 10, 7}, {9, 17, 12}, {8, 1, 14}})));
    }
}
